package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/search-a-2d-matrix/
 *
 * @author haoyang.shi
 */
public class Array74 {

  @Test
  public void test() {
    System.out.println(
        searchMatrix(
            new int[][] {
              {1, 3, 5, 7},
              {10, 11, 16, 20},
              {23, 30, 34, 50}
            },
            3));

    System.out.println(
        searchMatrix(
            new int[][] {
              {1, 3, 5, 7},
              {10, 11, 16, 20},
              {23, 30, 34, 50}
            },
            13));
  }

  public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0) {
      return false;
    }

    if (matrix.length == 1) {
      return divideFind(matrix[0], target);
    }

    int i = 0;
    for (; i < matrix.length; i++) {
      if (matrix[i].length == 0) {
        continue;
      }

      if (matrix[i][0] > target) {
        break;
      }
    }

    if (i == 0) {
      return false;
    }

    return divideFind(matrix[i - 1], target);
  }

  private boolean divideFind(int[] nums, int target) {
    if (nums.length == 0) {
      return false;
    }

    if (nums[0] > target) {
      return false;
    }

    int start = 0;
    int end = nums.length - 1;

    while (start < end) {
      int mid = (start + end) / 2;
      if (nums[mid] == target) {
        return true;
      } else if (nums[mid] > target) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }

    return nums[start] == target;
  }
}
